#include<iostream>
using namespace std;
//结点实现
template<class K, size_t M>
struct BTreeNode
{
	//K _keys[M - 1];
	//BTreeNode<K, M>* _subs[M];

	K _keys[M];
	BTreeNode<K, M>* _subs[M+1];
	BTreeNode<K, M>* _parent;
	size_t _n;

	BTreeNode()
	{
		for (size_t i = 0; i < M; ++i)
		{
			_keys[i] = K();
			_subs[i] = nullptr;
		}

		_subs[M] = nullptr;
		_parent = nullptr;
		_n = 0;
	}
};


//B树
template<class K, size_t M>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:


	//查找
	pair<Node*, int> Find(const K& key)
	{
		Node* parent = nullptr;
		Node* cur = _root;

		while (cur)
		{

			size_t i = 0;
			while (i < cur->_n)
			{
				if (key < cur->_keys[i])
				{
					break;
				}
				else if (key > cur->_keys[i])
				{
					++i;
				}
				else
				{
					return make_pair(cur, i);
				}
			}

			parent = cur;
			cur = cur->_subs[i];
		}
		
		return make_pair(parent, -1);
	}


	//插入关键字和孩子
	void InsertKey(Node* node, const K& key, Node* child)
	{
		int end = node->_n - 1;
		while (end >= 0)
		{
			if (key < node->_keys[end])
			{
	
				node->_keys[end + 1] = node->_keys[end];
				node->_subs[end + 2] = node->_subs[end + 1];
 				--end;
			}
			else
			{
				break;
			}
		}

		node->_keys[end + 1] = key;
		node->_subs[end + 2] = child;
		if (child)
		{
			child->_parent = node;
		}

		node->_n++;
	}

	//插入关键字
	bool Insert(const K& key)
	{
		if (_root == nullptr)
		{
			_root = new Node;
			_root->_keys[0] = key;
			_root->_n++;

			return true;
		}

		pair<Node*, int> ret = Find(key);
		if (ret.second >= 0)
		{
			return false;
		}

		Node* parent = ret.first;
		K newKey = key;
		Node* child = nullptr;
		while (1)
		{
			InsertKey(parent, newKey, child);
			if (parent->_n < M)
			{
				return true;
			}
			else
			{
				size_t mid = M / 2;
				Node* brother = new Node;
				size_t j = 0;
				size_t i = mid + 1;
				for (; i <= M - 1; ++i)
				{
					brother->_keys[j] = parent->_keys[i];
					brother->_subs[j] = parent->_subs[i];
					if (parent->_subs[i])
					{
						parent->_subs[i]->_parent = brother;
					}
					++j;

					parent->_keys[i] = K();
					parent->_subs[i] = nullptr;
				}

				brother->_subs[j] = parent->_subs[i];
				if (parent->_subs[i])
				{
					parent->_subs[i]->_parent = brother;
				}
				parent->_subs[i] = nullptr;

				brother->_n = j;
				parent->_n -= (brother->_n + 1);

				K midKey = parent->_keys[mid];
				parent->_keys[mid] = K();



				if (parent->_parent == nullptr)
				{
					_root = new Node;
					_root->_keys[0] = midKey;
					_root->_subs[0] = parent;
					_root->_subs[1] = brother;
					_root->_n = 1;

					parent->_parent = _root;
					brother->_parent = _root;
					break;
				}
				else
				{
					newKey = midKey;

					child = brother;
					parent = parent->_parent;
				}
			}
		}
		
		return true;
	}

	void _InOrder(Node* cur)
	{
		if (cur == nullptr)
			return;

		size_t i = 0;
		for (; i < cur->_n; ++i)
		{
			_InOrder(cur->_subs[i]); 
			cout << cur->_keys[i] << " "; 
		}

		_InOrder(cur->_subs[i]); 
	}


	//中序遍历
	void InOrder()
	{
		_InOrder(_root);
        cout<<endl;
	}

private:
	Node* _root = nullptr;
};